We consider the Set Once Strip Cover problem, in which n wireless sensors aredeployed over a one-dimensional region. Each sensor has a fixed battery thatdrains in inverse proportion to a radius that can be set just once, butactivated at any time. The problem is to find an assignment of radii andactivation times that maximizes the length of time during which the entireregion is covered. We show that this problem is NP-hard. Second, we show thatRoundRobin, the algorithm in which the sensors simply take turns covering theentire region, has a tight approximation guarantee of 3/2 in both Set OnceStrip Cover and the more general Strip Cover problem, in which each radius maybe set finitely-many times. Moreover, we show that the more general class ofduty cycle algorithms, in which groups of sensors take turns covering theentire region, can do no better. Finally, we give an optimal O(n^2 log n)-timealgorithm for the related Set Radius Strip Cover problem, in which all sensorsmust be activated immediately.
展开▼
